Computer-based image-processing and image-analysis techniques may be used to detect shapes (e.g., lines, circles, or ellipses) in digitized images. Images from vehicle-mounted cameras, for example, may be analyzed for lines and other content therein; particular applications in this field include driver-assistance systems that recognize lane markers on a road by identifying them as lines. These systems may then determine where in a lane the driven vehicle is located and, for example, warn the driver of the vehicle if it drifts too close to a lane boundary. A fast and robust line-detection method, capable of accurate real-time analysis, is required for such systems. One such method uses a technique known as a Hough transform that, among other advantages, is capable of detecting lines in noisy images and in images having variations in brightness.
The image captured from the vehicle-mounted camera is first pre-processed to identify edges in the image (using, for example, a Sobel or Prewitt operator), thereby creating an “edge image.” The Hough transform is then used to determine which edges in the edge image are lines by first converting the data in the image from “image space” to “Hough space.” Image space refers to the expression of the usual (x,y) coordinate data in an image, in which a line may be expressed using equation (1), as shown below.y=mx+b  (1)In equation (1), m is the slope of the line and b is the position the line intercepts the y-axis. In Hough space, this same line is expressed using a first parameter ρ, which is the shortest distance between the line and the origin, and a second parameter θ, which is the angle this shortest line makes with the x-axis. In general, lines in Hough space may be expressed using the relationship shown below in equation (2).ρ=x cos θ+y sin θ  (2)Notably, a line in image space reduces to a single point in Hough space of coordinate (ρ,θ), while non-linear shapes in image space produce curves or other non-point shapes in Hough space.
In theory, then, the converted Hough-space data may simply be searched for single points, the locations of which reveal which edges in image space correspond to lines. In practice, the Hough transform converts and searches the (x,y) edge-pixel data by calculating a number of ρ values for a predetermined set of θ values, using equation (2), for each (x,y) edge pixel. A two-dimensional array of size ρ×θ (an “accumulator array”) is maintained; each cell in the array accumulates a running tally, or “votes,” of the number of times a particular (ρ,θ) pair has been calculated (and rounded up or down to the cell in the array having the nearest value). Because a group of (x,y) edge pixels belonging to a straight line produces the same (ρ,θ) pair more often than a group of (x,y) edge pixels that do not correspond to a straight line, higher vote counts in the two-dimensional accumulator array denote (ρ,θ) pairs corresponding to lines. The votes in the two-dimensional accumulator array may thus be searched for local maxima, which correspond to lines in the (x,y) space of the original image.
An example may further illustrate the relationship between image space and Hough space. A simplified representation of a roadway 100 and its corresponding Hough transform 200 are shown in FIGS. 1A and 1B, respectively. The roadway scene 100 includes center lane markers 102a, 104a and boundary lane markers 106a, 108a as well as a car 110a in one lane and other objects 112a, 114a, 116a outside the lanes. A (0,0) origin 118 in the (x,y) image space shown in the roadway scene 100 is disposed in the approximate center of the scene 100. As explained above, lines in image space reduce to points in Hough space; in the Hough space 150 depicted in FIG. 1B, the lines 102a, 104a, 106a, 108a correspond to points 102b, 104b, 106b, 108b (note that, however, artifacts in the conversion procedure used to produce FIG. 1B produce noise around the points 102b, 104b, 106b, 108b). Because the center lane markers 102a, 104a lie close to the origin 118, their ρ values (i.e., the shortest distances between the lines 102a, 104a and the origin 118) are small, as reflected by their corresponding points 102b, 104b in the Hough space 150. Because the points 102a, 104a lie on opposite sides of the origin 118, their θ values are approximately equal and opposite, as again reflected in the Hough space 150. The boundary lane markers 106a, 108a, being farther from the origin 118, have greater ρ values, as shown. The other objects 110a, 112a, 114a, 116a in the roadway scene 100 are composed of many curved lines and other shapes and thus transform into bands 110b, 112b, 114b, 116b of (ρ,θ) pairs.
A computer processor that implements the Hough transform stores the edge image in memory and may require access to any part of the edge image at any time, depending on where the edges are located in it. In addition, existing systems and methods require a large, two-dimensional accumulator array to tally the votes for the ρ and θ values; both of these requirements depend on fast memory. Typically, memory in a computer system is arranged hierarchically, with relatively small and fast (but expensive) memory located near the processor and relatively large and slow (but cheap) memory located further from the processor. Note that, in this application, the term “local memory” is used to refer to the fast memory, but this term is not meant to be limiting and may apply to any kind of register file, cache, L1 or L2 memory, or any other type of memory closer in hierarchy to the processor than the large, slow memory (herein referred to as “main” or “system” memory).
The large sizes of the two-dimensional accumulator array and edge image, as well as the Hough transform's unpredictable “random” access to them, not only means that they cannot fit in local memory but also that portions of the accumulator array and edge image cannot be efficiently cached; unless the local memory or cache is large enough to store the entire edge image and accumulator array, the Hough transform will run very slowly as it makes repeated, random accesses to a remote main memory. Modern desktop-computer processors may have large enough local memories to run the Hough transform well, but low-power mobile or digital-signal processors, such as the ones used in vehicle-based image-detection systems, do not. The problem only becomes worse with the ongoing development of low-cost, high-resolution digital cameras that create digital images of ever-increasing size. A need therefore exists for an efficient line-detection system capable of running quickly on a processor having limited local memory.